package com.yanceysong.codetop.s91_s100;

public class S97_Mid_718_最长重复子数组 {
    /**
     * .S97_Mid_718_最长重复子数组
     * .<p>
     * .<a href="https://leetcode.cn/problems/maximum-length-of-repeated-subarray/">...</a>
     * .<p>
     * .给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。
     * .<p>
     * .示例：
     * .<p>
     * .输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
     * .输出：3
     * .解释：长度最长的公共子数组是 [3,2,1] 。
     * .<p>
     * .输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
     * .输出：5
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums1.length, nums2.length <= 1000
     * .0 <= nums1[i], nums2[i] <= 100
     * .<p>
     * .核心标签：数组、动态规划、滑动窗口、二分查找、哈希
     * .<p>
     * .算法原理：动态规划
     * .- 定义 dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子数组的长度
     * .- 状态转移方程：
     * .- 如果 nums1[i] == nums2[j]，则 dp[i][j] = dp[i+1][j+1] + 1
     * .- 如果 nums1[i] != nums2[j]，则 dp[i][j] = 0（子数组必须连续）
     * .- 从后向前遍历，避免状态覆盖问题
     * .- 最终答案是 dp 数组中的最大值
     * .<p>
     * .关键洞察：
     * .1. 子数组必须是连续的，这与子序列（可以不连续）不同
     * .2. 当两个元素不相等时，以它们结尾的公共子数组长度必为 0
     * .3. 当两个元素相等时，长度等于它们后面的公共子数组长度 + 1
     * .4. 需要记录过程中的最大值，而不是只看最后一个状态
     * .5. 从后向前遍历可以避免使用额外空间或状态覆盖问题
     * .<p>
     * .图解示例：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
     * .<p>
     * .构建 dp 表格（从后向前填充）：
     * .<p>
     * .nums2 →  3  2  1  4  7
     * .nums1 ↓
     * .1      [0][0][1][0][0]
     * .2      [0][1][0][0][0]
     * .3      [1][0][0][0][0]
     * .2      [0][2][0][0][0]
     * .1      [0][0][3][0][0]
     * .<p>
     * .详细填充过程（从右下角开始）：
     * .<p>
     * .初始状态：所有 dp[i][j] = 0
     * .<p>
     * .i=4, j=4: nums1[4]=1, nums2[4]=7
     * .1 != 7 → dp[4][4] = 0
     * .<p>
     * .i=4, j=3: nums1[4]=1, nums2[3]=4
     * .1 != 4 → dp[4][3] = 0
     * .<p>
     * .i=4, j=2: nums1[4]=1, nums2[2]=1
     * .1 == 1 → dp[4][2] = dp[5][3] + 1 = 0 + 1 = 1 ✓
     * .maxLen = 1
     * .<p>
     * .i=4, j=1: nums1[4]=1, nums2[1]=2
     * .1 != 2 → dp[4][1] = 0
     * .<p>
     * .i=4, j=0: nums1[4]=1, nums2[0]=3
     * .1 != 3 → dp[4][0] = 0
     * .<p>
     * .i=3, j=4: nums1[3]=2, nums2[4]=7
     * .2 != 7 → dp[3][4] = 0
     * .<p>
     * .i=3, j=3: nums1[3]=2, nums2[3]=4
     * .2 != 4 → dp[3][3] = 0
     * .<p>
     * .i=3, j=2: nums1[3]=2, nums2[2]=1
     * .2 != 1 → dp[3][2] = 0
     * .<p>
     * .i=3, j=1: nums1[3]=2, nums2[1]=2
     * .2 == 2 → dp[3][1] = dp[4][2] + 1 = 1 + 1 = 2 ✓
     * .maxLen = 2
     * .<p>
     * .i=3, j=0: nums1[3]=2, nums2[0]=3
     * .2 != 3 → dp[3][0] = 0
     * .<p>
     * .i=2, j=2: nums1[2]=3, nums2[2]=1
     * .3 != 1 → dp[2][2] = 0
     * .<p>
     * .i=2, j=1: nums1[2]=3, nums2[1]=2
     * .3 != 2 → dp[2][1] = 0
     * .<p>
     * .i=2, j=0: nums1[2]=3, nums2[0]=3
     * .3 == 3 → dp[2][0] = dp[3][1] + 1 = 2 + 1 = 3 ✓
     * .maxLen = 3（最长公共子数组：[3,2,1]）
     * .<p>
     * .继续填充其余位置...
     * .<p>
     * .最终 dp 表格：
     * .<p>
     * .j→  0  1  2  3  4
     * .i↓
     * .0   0  0  1  0  0    nums1[0]=1
     * .1   0  1  0  0  0    nums1[1]=2
     * .2   1  0  0  0  0    nums1[2]=3
     * .3   0  2  0  0  0    nums1[3]=2
     * .4   0  0  3  0  0    nums1[4]=1
     * .<p>
     * .nums2: [3, 2, 1, 4, 7]
     * .<p>
     * .找到最大值：dp[4][2] = 3
     * .对应的公共子数组：nums1[2:5] = [3,2,1], nums2[0:3] = [3,2,1]
     * .<p>
     * .状态转移图示：
     * .<p>
     * .当 nums1[i] == nums2[j] 时：
     * .<p>
     * .nums1: ... [3] [2] [1] ...
     * .↓   ↓   ↓
     * .nums2: ... [3] [2] [1] ...
     * .<p>
     * .dp[2][0] = 1 (匹配 3)
     * .↓
     * .dp[3][1] = 2 (匹配 3,2)
     * .↓
     * .dp[4][2] = 3 (匹配 3,2,1)
     * .<p>
     * .为什么从后向前遍历？
     * .<p>
     * .因为 dp[i][j] 依赖于 dp[i+1][j+1]
     * .从后向前可以保证计算 dp[i][j] 时，dp[i+1][j+1] 已经计算完成
     * .<p>
     * .时间复杂度：O(n × m)，其中 n 和 m 分别为两个数组的长度
     * .- 需要填充整个 dp 表格，每个位置计算一次
     * .<p>
     * .空间复杂度：O(n × m)
     * .- 需要一个二维 dp 数组存储状态
     * .- 可以优化到 O(min(n, m))，使用滚动数组
     */
    public int findLength(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;

        // dp[i][j] 表示以 nums1[i] 和 nums2[j] 结尾的最长公共子数组的长度
        int[][] dp = new int[length1 + 1][length2 + 1];

        // 记录最长公共子数组的长度
        int maxLength = 0;

        // 从后向前遍历，避免状态覆盖问题
        for (int i = length1 - 1; i >= 0; i--) {
            for (int j = length2 - 1; j >= 0; j--) {
                // 如果当前元素相等
                if (nums1[i] == nums2[j]) {
                    // 当前位置的长度 = 后一个位置的长度 + 1
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                    // 更新最大长度
                    maxLength = Math.max(maxLength, dp[i][j]);
                } else {
                    // 如果元素不相等，以它们结尾的公共子数组长度为 0
                    dp[i][j] = 0;
                }
            }
        }

        return maxLength;
    }

    public static void main(String[] args) {
        S97_Mid_718_最长重复子数组 solution = new S97_Mid_718_最长重复子数组();

        System.out.println("=== 最长重复子数组测试开始 ===");

        // 测试1: 题目示例1 - nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
        System.out.println("\n--- 测试1: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
        System.out.println("\n--- 测试2: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0] ---");
        testCase2(solution);

        // 测试3: 没有公共子数组
        System.out.println("\n--- 测试3: 没有公共子数组 ---");
        testNoCommon(solution);

        // 测试4: 完全相同的数组
        System.out.println("\n--- 测试4: 完全相同的数组 ---");
        testIdenticalArrays(solution);

        // 测试5: 一个数组是另一个的子数组
        System.out.println("\n--- 测试5: 一个数组是另一个的子数组 ---");
        testSubarray(solution);

        // 测试6: 单元素数组，相同
        System.out.println("\n--- 测试6: 单元素数组，相同 ---");
        testSingleElementSame(solution);

        // 测试7: 单元素数组，不同
        System.out.println("\n--- 测试7: 单元素数组，不同 ---");
        testSingleElementDifferent(solution);

        // 测试8: 公共子数组在开头
        System.out.println("\n--- 测试8: 公共子数组在开头 ---");
        testCommonAtStart(solution);

        // 测试9: 公共子数组在末尾
        System.out.println("\n--- 测试9: 公共子数组在末尾 ---");
        testCommonAtEnd(solution);

        // 测试10: 公共子数组在中间
        System.out.println("\n--- 测试10: 公共子数组在中间 ---");
        testCommonInMiddle(solution);

        // 测试11: 多个公共子数组，取最长
        System.out.println("\n--- 测试11: 多个公共子数组，取最长 ---");
        testMultipleCommon(solution);

        // 测试12: 大数组测试
        System.out.println("\n--- 测试12: 大数组测试 ---");
        testLargeArrays(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
     * .期望输出：3（公共子数组 [3,2,1]）
     */
    private static void testCase1(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 2, 1};
        int[] nums2 = {3, 2, 1, 4, 7};

        System.out.println("输入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: 长度最长的公共子数组是 [3,2,1]");

        assert result == 3 : "测试1失败：期望3，实际" + result;
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
     * .期望输出：5
     */
    private static void testCase2(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {0, 0, 0, 0, 0};
        int[] nums2 = {0, 0, 0, 0, 0};

        System.out.println("输入: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 5)");
        System.out.println("解释: 整个数组都是公共子数组");

        assert result == 5 : "测试2失败：期望5，实际" + result;
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 没有公共子数组
     * .期望输出：0
     */
    private static void testNoCommon(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3};
        int[] nums2 = {4, 5, 6};

        System.out.println("输入: nums1 = [1,2,3], nums2 = [4,5,6]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 0)");
        System.out.println("解释: 没有公共元素");

        assert result == 0 : "测试3失败：期望0，实际" + result;
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 完全相同的数组
     * .期望输出：数组长度
     */
    private static void testIdenticalArrays(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {1, 2, 3, 4, 5};

        System.out.println("输入: nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 5)");
        System.out.println("解释: 两个数组完全相同");

        assert result == 5 : "测试4失败：期望5，实际" + result;
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 一个数组是另一个的子数组
     * .期望输出：较短数组的长度
     */
    private static void testSubarray(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7};
        int[] nums2 = {3, 4, 5};

        System.out.println("输入: nums1 = [1,2,3,4,5,6,7], nums2 = [3,4,5]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: nums2 是 nums1 的子数组");

        assert result == 3 : "测试5失败：期望3，实际" + result;
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 单元素数组，相同
     * .期望输出：1
     */
    private static void testSingleElementSame(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {5};
        int[] nums2 = {5};

        System.out.println("输入: nums1 = [5], nums2 = [5]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 1)");

        assert result == 1 : "测试6失败：期望1，实际" + result;
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 单元素数组，不同
     * .期望输出：0
     */
    private static void testSingleElementDifferent(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {5};
        int[] nums2 = {3};

        System.out.println("输入: nums1 = [5], nums2 = [3]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 0)");

        assert result == 0 : "测试7失败：期望0，实际" + result;
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 公共子数组在开头
     * .期望输出：3
     */
    private static void testCommonAtStart(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {1, 2, 3, 6, 7};

        System.out.println("输入: nums1 = [1,2,3,4,5], nums2 = [1,2,3,6,7]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: 公共子数组 [1,2,3] 在开头");

        assert result == 3 : "测试8失败：期望3，实际" + result;
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 公共子数组在末尾
     * .期望输出：3
     */
    private static void testCommonAtEnd(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {6, 7, 3, 4, 5};

        System.out.println("输入: nums1 = [1,2,3,4,5], nums2 = [6,7,3,4,5]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: 公共子数组 [3,4,5] 在末尾");

        assert result == 3 : "测试9失败：期望3，实际" + result;
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 公共子数组在中间
     * .期望输出：3
     */
    private static void testCommonInMiddle(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5, 6};
        int[] nums2 = {7, 8, 3, 4, 5, 9};

        System.out.println("输入: nums1 = [1,2,3,4,5,6], nums2 = [7,8,3,4,5,9]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 3)");
        System.out.println("解释: 公共子数组 [3,4,5] 在中间");

        assert result == 3 : "测试10失败：期望3，实际" + result;
        System.out.println("✓ 测试10通过");
    }

    /**
     * .测试11: 多个公共子数组，取最长
     * .期望输出：4
     */
    private static void testMultipleCommon(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] nums2 = {1, 2, 9, 5, 6, 7, 8, 10};

        System.out.println("输入: nums1 = [1,2,3,4,5,6,7,8], nums2 = [1,2,9,5,6,7,8,10]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 4)");
        System.out.println("解释: 有 [1,2] 和 [5,6,7,8]，最长的是 [5,6,7,8]");

        assert result == 4 : "测试11失败：期望4，实际" + result;
        System.out.println("✓ 测试11通过");
    }

    /**
     * .测试12: 大数组测试
     * .期望输出：合理的结果
     */
    private static void testLargeArrays(S97_Mid_718_最长重复子数组 solution) {
        int[] nums1 = new int[100];
        int[] nums2 = new int[100];

        // 填充数组：前50个元素为 1-50，后50个元素为 51-100
        for (int i = 0; i < 100; i++) {
            nums1[i] = i + 1;
        }

        // nums2: 前10个元素为 91-100，中间50个元素为 41-90，后40个元素为 101-140
        for (int i = 0; i < 10; i++) {
            nums2[i] = 91 + i;
        }
        for (int i = 10; i < 60; i++) {
            nums2[i] = 31 + i; // 41-90
        }
        for (int i = 60; i < 100; i++) {
            nums2[i] = 41 + i; // 101-140
        }

        System.out.println("输入: nums1 = [1,2,...,100], nums2 = [91,...,100,41,...,90,101,...,140]");
        int result = solution.findLength(nums1, nums2);
        System.out.println("输出: " + result + " (期望: 50)");
        System.out.println("解释: 公共子数组 [41,42,...,90] 长度为 50");

        assert result == 50 : "测试12失败：期望50，实际" + result;
        System.out.println("✓ 测试12通过");
    }
}

